/*
 * @lc app=leetcode id=445 lang=cpp
 *
 * [445] Add Two Numbers II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int n = 0;
        int m = 0;
        ListNode *p = l1;
        while (p) {
            p = p->next;
            n++;
        }
        ListNode *q = l2;
        while (q) {
            q = q->next;
            m++;
        }
        ListNode *root;
        if (n >= m) {
            root =   Add(l1, l2, n - m);
        } else {
            root =  Add(l2, l1, m - n);
        }
        if (root->val >=10 ){
            ListNode *node = new ListNode(1, root);
            root->val -= 10;
            node->next = root;
            return node;
        }
        return root;

        
    }
    ListNode *Add(ListNode *p, ListNode *q, int n) {
        if (n > 0) {
            ListNode *node = Add(p->next, q, n - 1);
            int val = p->val + (node->val >= 10? 1 : 0);
            node->val = node->val >= 10? node->val - 10 : node->val;
            ListNode *new_node = new ListNode(val, node);
            return new_node;
        } else {
            ListNode *node = Add2(p, q);
            return node;
        }
    }

    ListNode *Add2(ListNode *p, ListNode *q) {
        if (p->next && q->next) {
            ListNode *node = Add2(p->next, q->next);
            int val = p->val + q->val + (node->val  >=10 ? 1 : 0);
            node->val = node->val >= 10? node->val - 10 : node->val;
            ListNode *new_node = new ListNode(val, node);
            return new_node;
        } else if (p && q) {
            int val = p->val + q ->val;
            ListNode *new_node = new ListNode(val);
            return new_node;
        }  else {
            return nullptr;
        }
        
        
    }


};
// @lc code=end

